using BepuUtilities.Collections;
using BepuUtilities.Memory;
using System.Diagnostics;
using System.Runtime.CompilerServices;

namespace BepuUtilities.Collections
{
    public static class QuickSort
    {

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<T>(ref T a, ref T b)
        {
            var temp = a;
            a = b;
            b = temp;
        }

        // TODO：如果JIT曾经设法以最佳方式处理ISPAN索引器,我们可以使用更自然的基于ISPAN的实现。

        // [MethodImpl(MethodImplOptions.AggressiveInlining)]
        // 静电无效交换<TKey,TValue,TKeySpan,TValueSpan>(引用TKeySpan键,引用TValueSpan值,int a,int b)
        // 其中TKeySpan：isspan<TKey>
        // 其中TValueSpan：isspan<TValue>
        // {
        // 交换(引用键[a],引用键[b]);
        // 交换(引用值[a],引用值[b]);
        // }

        // [MethodImpl(MethodImplOptions.AggressiveInlining)]
        // 公共静电int FindMO3Index<TKEY,TKEYSPAN,T比较器>(REF TKEYSPAN KEYS,INT l,INT r,REF T比较器)
        // 其中,TCompeller：IComperRef<TKey>
        // 其中TKeySpan：isspan<TKey>
        // {
        // //使用MO3查找枢轴,以补偿常见的已排序情况,并略微改善最坏情况的行为。
        // var first=密钥[l];
        // int midleIndex=(l+r)/2;
        // var midd=KEYS[midleIndex];
        // var last=密钥[r];
        // IF(比较.Compare(参考第一,参考中间)<=0&&比较.Compare(参考第一,参考最后)<=0)
        // {
        // //First是最低的。
        // IF(比较.Compare(参考中间,参考最后)<=0)
        // {
        // 返回midleIndex;
        // }
        // 其他
        // {
        // 返回r;
        // }
        // }
        // ELSE IF(比较.Compare(参考中间,参考最后)<=0)
        // {
        // //中间是最低的。
        // IF(比较.Compare(参考第一,参考最后)<=0)
        // {
        // 返回l;
        // }
        // 其他
        // {
        // 返回r;
        // }
        // }
        // 其他
        // {
        // //最后一个是最低的。
        // IF(比较.Compare(参考第一,参考中间)<=0)
        // {
        // 返回l;
        // }
        // 其他
        // {
        // 返回midleIndex;
        // }
        // }
        // }

        // 公共静电空排序与三个路径分区<TKey,TValue,TKeySpan,TValueSpan,TCompeller>
        // (引用TKeySpan关键字,引用TValueSpan值,int l,int r,引用TCompeller比较器)
        // 其中,TCompeller：IComperRef<TKey>
        // 其中TKeySpan：isspan<TKey>
        // 其中TValueSpan：isspan<TValue>
        // {
        // IF(r-l<=30)
        // {
        // //要寻址的区域很小。使用插入排序。
        // InsertionSort.Sort<TKey,TValue,TKeySpan,TValueSpan,TCompeller>(引用关键字,引用值,l,r,引用比较器);
        // }
        // 其他
        // {
        // //使用MO3查找枢轴,以补偿常见的已排序情况,并略微改善最坏情况的行为。
        // var PivotIndex=FindMO3Index<TKey,TKeySpan,TCompeller>(ref key,l,r,ref compeller);

        // //将枢轴放入最后一个槽中。
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,透视索引,r);
        // ref var轴心=ref关键字[r];

        // //使用Bentley-McIlroy三向分区方案,避免角落情况下的性能下降
        // int i=l-1;//在分区区域下面开始一个索引,因为不知道第一个索引是否实际可声明。
        // int j=r;//分区的最后一个元素持有透视,它被排除在交换过程之外。与i的逻辑相同。
        // int p=l-1;
        // int q=r;
        // 如果(r<=l)
        // 返回;
        // WHILE(TRUE)
        // {
        // //认领左右两边分区的列表分块
        // WHILE(TRUE)
        // {
        // ++i;
        // if(comper.Compare(引用关键字[i],引用枢轴)>=0)
        // 断线;
        // }
        // WHILE(TRUE)
        // {
        // --j;
        // if(comper.Compare(ref Pivot,ref keys[j])>=0||j==l)
        // 断线;

        // }
        // //如果声明满足,则分区完成。
        // 如果(i>=j)
        // {
        // 断线;
        // }
        // //通过上面的声明,并且因为我们还没有脱离循环,
        // //i关联的值>=透视,j关联的值<=透视
        // //所以调换一下。
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,i,j);
        // IF(比较.Compare(参考关键字[i],参考枢轴)==0)
        // {
        // P++;
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,p,i);
        // }
        // if(comper.Compare(参考枢轴,参考关键字[j])==0)
        // {
        // Q--;
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,j,q);
        // }
        // }
        // //尚未交换%r处的轴心点。
        // //由于循环已经终止,我们知道我已经到达分区的‘>=PIVOT’端。
        // //因此,将透视和大于透视侧的第一个元素互换以保证排序。
        // //请注意,这会使前面的‘Pivot’变量无效;它是byref。但我们不再用它了,所以没关系。
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,i,r);
        // J=I-1;
        // i=i+1;
        // for(int k=l;k<p;k++,j-)
        // {
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,k,j);
        // }
        // for(int k=r-1;k>q;k--,i++)
        // {
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,i,k);
        // }
        // SortWithThreeWayPartitioning<TKey,TValue,TKeySpan,TValueSpan,TCompeller>(引用关键字,引用值,l,j,引用比较器);
        // SortWithThreeWayPartitioning<TKey,TValue,TKeySpan,TValueSpan,TCompeller>(引用关键字,引用值,i,r,引用比较器);
        // }
        // }


        // 公共静电无效排序<Tkey,TValue,TKeySpan,TValueSpan,TCompeller>
        // (引用TKeySpan关键字,引用TValueSpan值,int l,int r,引用TCompeller比较器)
        // 其中,TCompeller：IComperRef<TKey>
        // 其中TKeySpan：isspan<TKey>
        // 其中TValueSpan：isspan<TValue>
        // {
        // IF(r-l<=30)
        // {
        // //要寻址的区域很小。使用插入排序。
        // InsertionSort.Sort<TKey,TValue,TKeySpan,TValueSpan,TCompeller>(引用关键字,引用值,l,r,引用比较器);
        // }
        // 其他
        // {
        // //使用MO3查找枢轴,以补偿常见的已排序情况,并略微改善最坏情况的行为。
        // var PivotIndex=FindMO3Index<TKey,TKeySpan,TCompeller>(ref key,l,r,ref compeller);

        // //将枢轴放入最后一个槽中。
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,透视索引,r);
        // ref var轴心=ref关键字[r];

        // int i=l-1;//在分区区域下面开始一个索引,因为不知道第一个索引是否实际可声明。
        // int j=r;//分区的最后一个元素持有透视,它被排除在交换过程之外。与i的逻辑相同。
        // WHILE(TRUE)
        // {
        // //认领左右两边分区的列表分块
        // WHILE(TRUE)
        // {
        // ++i;
        // if(comper.Compare(引用关键字[i],引用枢轴)>=0)
        // 断线;
        // }
        // WHILE(TRUE)
        // {
        // --j;
        // if(comper.Compare(ref Pivot,ref keys[j])>=0||j<=i)
        // 断线;

        // }
        // //如果声明满足,则分区完成。
        // 如果(i>=j)
        // {
        // 断线;
        // }
        // //通过上面的声明,并且因为我们还没有脱离循环,
        // //i关联的值>=透视,j关联的值<=透视
        // //所以调换一下。
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,i,j);
        // }
        // //未重新引入枢轴。
        // //由于循环已经终止,我们知道我已经到达分区的‘>=PIVOT’端。
        // //因此,将大于轴一侧的第一个元素推入r,并将轴推入第一个较大元素的槽中,以确保排序。
        // 交换<TKey,TValue,TKeySpan,TValueSpan>(引用关键字,引用值,i,r);
        // j=i-1;//排序的参数采用包含边界,因此将j推回。
        // i=i+1;//透视占据了i的位置,排序中不应该包含透视,所以将i向上推。
        // Debug.Assert(i<=r);
        // Debug.Assert(j>=l);
        // 排序<TKey,TValue,TKeySpan,TValueSpan,TCompeller>(引用关键字,引用值,l,j,引用比较器);
        // 排序<TKey,TValue,TKeySpan,TValueSpan,TCompeller>(引用关键字,引用值,i,r,引用比较器);
        // }
        // }




        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<TKey, TValue>(ref TKey keys, ref TValue values, int a, int b)
        {
            Swap(ref Unsafe.Add(ref keys, a), ref Unsafe.Add(ref keys, b));
            Swap(ref Unsafe.Add(ref values, a), ref Unsafe.Add(ref values, b));
        }

        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        static void Swap<TKey>(ref TKey keys, int a, int b)
        {
            Swap(ref Unsafe.Add(ref keys, a), ref Unsafe.Add(ref keys, b));
        }


        [MethodImpl(MethodImplOptions.AggressiveInlining)]
        public static int FindMO3Index<TKey, TComparer>(ref TKey keys, int l, int r, ref TComparer comparer)
            where TComparer : IComparerRef<TKey>
        {
            // 使用MO3找到一个支点,以补偿常见的已排序情况,并略微改善最坏情况下的行为。
            ref var first = ref Unsafe.Add(ref keys, l);
            int middleIndex = (l + r) / 2;
            ref var middle = ref Unsafe.Add(ref keys, middleIndex);
            ref var last = ref Unsafe.Add(ref keys, r);
            if (comparer.Compare(ref first, ref middle) <= 0 && comparer.Compare(ref first, ref last) <= 0)
            {
                // 第一是最低的。
                if (comparer.Compare(ref middle, ref last) <= 0)
                {
                    return middleIndex;
                }
                else
                {
                    return r;
                }
            }
            else if (comparer.Compare(ref middle, ref last) <= 0)
            {
                // 中间是最低的。
                if (comparer.Compare(ref first, ref last) <= 0)
                {
                    return l;
                }
                else
                {
                    return r;
                }
            }
            else
            {
                // 最后一个是最低的。
                if (comparer.Compare(ref first, ref middle) <= 0)
                {
                    return l;
                }
                else
                {
                    return middleIndex;
                }
            }
        }

        public static void SortWithThreeWayPartitioning<TKey, TValue, TComparer>(ref TKey keys, ref TValue values, int l, int r, ref TComparer comparer) where TComparer : IComparerRef<TKey>
        {
            if (r - l <= 30)
            {
                // 要解决的区域非常小。使用插入排序。
                InsertionSort.Sort(ref keys, ref values, l, r, ref comparer);
            }
            else
            {
                // 使用MO3找到一个支点,以补偿常见的已排序情况,并略微改善最坏情况下的行为。
                var pivotIndex = FindMO3Index(ref keys, l, r, ref comparer);

                // 将枢轴放入最后一个插槽。
                var pivot = Unsafe.Add(ref keys, pivotIndex);
                var pivotValue = Unsafe.Add(ref values, pivotIndex);
                // 我们缓存了透视键和值。将‘r’中的值推到轴的位置,暂时不使用r。
                Unsafe.Add(ref keys, pivotIndex) = Unsafe.Add(ref keys, r);
                Unsafe.Add(ref values, pivotIndex) = Unsafe.Add(ref values, r);

                // 使用Bentley-McIlroy 3向分区方案,以避免在转角情况下性能下降。
                int i = l - 1; // 在分区区域下面开始一个索引,因为不知道第一个索引是否实际上是可声明的。
                int j = r; // 分区的最后一个元素持有从交换过程中排除的轴心。与i的逻辑相同。
                int p = l - 1;
                int q = r;
                if (r <= l)
                    return;
                while (true)
                {
                    // 认领左侧和右侧分区的列表块。
                    while (true)
                    {
                        ++i;
                        if (comparer.Compare(ref Unsafe.Add(ref keys, i), ref pivot) >= 0)
                            break;
                    }
                    while (true)
                    {
                        --j;
                        if (comparer.Compare(ref pivot, ref Unsafe.Add(ref keys, j)) >= 0 || j == l)
                            break;

                    }
                    // 如果声明已满足,则分区已完成。
                    if (i >= j)
                    {
                        break;
                    }
                    // 根据上面的说法,因为我们还没有脱离这个循环,
                    // 与i关联的值是>=轴心,与j关联的值是<=轴心。
                    // 那就互换吧。
                    Swap(ref keys, ref values, i, j);
                    if (comparer.Compare(ref Unsafe.Add(ref keys, i), ref pivot) == 0)
                    {
                        p++;
                        Swap(ref keys, ref values, p, i);
                    }
                    if (comparer.Compare(ref pivot, ref Unsafe.Add(ref keys, j)) == 0)
                    {
                        q--;
                        Swap(ref keys, ref values, j, q);
                    }
                }
                // 尚未交换r处的枢轴。
                // 由于循环已经终止,我们知道我已经到达分区的‘>=PIVOT’端。
                // 因此,交换透视图和大于透视图面的第一个元素以确保排序。
                ref var firstGreaterKeySlot = ref Unsafe.Add(ref keys, i);
                ref var firstGreaterValueSlot = ref Unsafe.Add(ref values, i);
                Unsafe.Add(ref keys, r) = firstGreaterKeySlot;
                Unsafe.Add(ref values, r) = firstGreaterValueSlot;
                firstGreaterKeySlot = pivot;
                firstGreaterValueSlot = pivotValue;
                j = i - 1;
                i = i + 1;
                for (int k = l; k < p; k++, j--)
                {
                    Swap(ref keys, ref values, k, j);
                }
                for (int k = r - 1; k > q; k--, i++)
                {
                    Swap(ref keys, ref values, i, k);
                }
                SortWithThreeWayPartitioning(ref keys, ref values, l, j, ref comparer);
                SortWithThreeWayPartitioning(ref keys, ref values, i, r, ref comparer);
            }
        }

        public static void Sort<TKey, TValue, TComparer>(ref TKey keys, ref TValue values, int l, int r, ref TComparer comparer) where TComparer : IComparerRef<TKey>
        {
            if (r - l <= 30)
            {
                // 要解决的区域非常小。使用插入排序。
                InsertionSort.Sort(ref keys, ref values, l, r, ref comparer);
            }
            else
            {
                // 使用MO3找到一个支点,以补偿常见的已排序情况,并略微改善最坏情况下的行为。
                var pivotIndex = FindMO3Index(ref keys, l, r, ref comparer);

                var pivot = Unsafe.Add(ref keys, pivotIndex);
                var pivotValue = Unsafe.Add(ref values, pivotIndex);
                // 我们缓存了透视键和值。将‘r’中的值推到轴的位置,暂时不使用r。
                Unsafe.Add(ref keys, pivotIndex) = Unsafe.Add(ref keys, r);
                Unsafe.Add(ref values, pivotIndex) = Unsafe.Add(ref values, r);

                int i = l - 1; // 在分区区域下面开始一个索引,因为不知道第一个索引是否实际上是可声明的。
                int j = r; // 分区的最后一个元素持有从交换过程中排除的轴心。与i的逻辑相同。
                while (true)
                {
                    // 认领左侧和右侧分区的列表块。
                    while (true)
                    {
                        ++i;
                        if (comparer.Compare(ref Unsafe.Add(ref keys, i), ref pivot) >= 0)
                            break;
                    }
                    while (true)
                    {
                        --j;
                        if (comparer.Compare(ref pivot, ref Unsafe.Add(ref keys, j)) >= 0 || j <= i)
                            break;

                    }
                    // 如果声明已满足,则分区已完成。
                    if (i >= j)
                    {
                        break;
                    }
                    // 根据上面的说法,因为我们还没有脱离这个循环,
                    // 与i关联的值是>=轴心,与j关联的值是<=轴心。
                    // 那就互换吧。
                    Swap(ref keys, ref values, i, j);
                }
                // 支点尚未重新引入。
                // 由于循环已经终止,我们知道我已经到达分区的‘>=PIVOT’端。
                // 因此,将大于轴一侧的第一个元素推入r,并将轴推入第一个较大元素的槽中,以确保排序。
                ref var firstGreaterKeySlot = ref Unsafe.Add(ref keys, i);
                ref var firstGreaterValueSlot = ref Unsafe.Add(ref values, i);
                Unsafe.Add(ref keys, r) = firstGreaterKeySlot;
                Unsafe.Add(ref values, r) = firstGreaterValueSlot;
                firstGreaterKeySlot = pivot;
                firstGreaterValueSlot = pivotValue;
                j = i - 1; // 排序的参数采用包含性界限,因此将j推回。
                i = i + 1; // 轴心占据了i的位置,并且轴心不应该包括在排序中,所以将i向上推。
                // 只有在有要排序的东西时才麻烦排序。
                if (j > l)
                    Sort(ref keys, ref values, l, j, ref comparer);
                if (r > i)
                    Sort(ref keys, ref values, i, r, ref comparer);
            }
        }
        public static void Sort<TKey, TComparer>(ref TKey keys, int l, int r, ref TComparer comparer) where TComparer : IComparerRef<TKey>
        {
            if (r - l <= 30)
            {
                // 要解决的区域非常小。使用插入排序。
                InsertionSort.Sort(ref keys, l, r, ref comparer);
            }
            else
            {
                // 使用MO3找到一个支点,以补偿常见的已排序情况,并略微改善最坏情况下的行为。
                var pivotIndex = FindMO3Index(ref keys, l, r, ref comparer);

                var pivot = Unsafe.Add(ref keys, pivotIndex);
                // 我们缓存了透视键和值。将‘r’中的值推到轴的位置,暂时不使用r。
                Unsafe.Add(ref keys, pivotIndex) = Unsafe.Add(ref keys, r);

                int i = l - 1; // 在分区区域下面开始一个索引,因为不知道第一个索引是否实际上是可声明的。
                int j = r; // 分区的最后一个元素持有从交换过程中排除的轴心。与i的逻辑相同。
                while (true)
                {
                    // 认领左侧和右侧分区的列表块。
                    while (true)
                    {
                        ++i;
                        if (comparer.Compare(ref Unsafe.Add(ref keys, i), ref pivot) >= 0)
                            break;
                    }
                    while (true)
                    {
                        --j;
                        if (comparer.Compare(ref pivot, ref Unsafe.Add(ref keys, j)) >= 0 || j <= i)
                            break;

                    }
                    // 如果声明已满足,则分区已完成。
                    if (i >= j)
                    {
                        break;
                    }
                    // 根据上面的说法,因为我们还没有脱离这个循环,
                    // 与i关联的值是>=轴心,与j关联的值是<=轴心。
                    // 那就互换吧。
                    Swap(ref keys, i, j);
                }
                // 支点尚未重新引入。
                // 由于循环已经终止,我们知道我已经到达分区的‘>=PIVOT’端。
                // 因此,将大于轴一侧的第一个元素推入r,并将轴推入第一个较大元素的槽中,以确保排序。
                ref var firstGreaterKeySlot = ref Unsafe.Add(ref keys, i);
                Unsafe.Add(ref keys, r) = firstGreaterKeySlot;
                firstGreaterKeySlot = pivot;
                j = i - 1; // 排序的参数采用包含性界限,因此将j推回。
                i = i + 1; // 轴心占据了i的位置,并且轴心不应该包括在排序中,所以将i向上推。
                // 只有在有要排序的东西时才麻烦排序。
                if (j > l)
                    Sort(ref keys, l, j, ref comparer);
                if (r > i)
                    Sort(ref keys, i, r, ref comparer);
            }
        }

    }
}
